Unique paths II¶
Time: O(MxN); Space: O(M+N); medium
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
Example 1:
Input: obstacleGrid =
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
Right -> Right -> Down -> Down
Down -> Down -> Right -> Right
Example 2:
Input: obstacleGrid = [[0]]
Output: 1
Constraints:
1 <= m, n <= 100
Hints:
The robot can only move either down or right. Hence any cell in the first row can only be reached from the cell left to it. However, if any cell has an obstacle, you don’t let that cell contribute to any path. So, for the first row, the number of ways will simply be
if obstacleGrid[i][j] is not an obstacle obstacleGrid[i,j] = obstacleGrid[i,j - 1] else obstacleGrid[i,j] = 0
You can do a similar processing for finding out the number of ways of reaching the cells in the first column.
For any other cell, we can find out the number of ways of reaching it, by making use of the number of ways of reaching the cell directly above it and the cell to the left of it in the grid. This is because these are the only two directions from which the robot can come to the current cell.
Since we are making use of pre-computed values along the iteration, this becomes a dynamic programming problem.
if obstacleGrid[i][j] is not an obstacle obstacleGrid[i,j] = obstacleGrid[i,j - 1] + obstacleGrid[i - 1][j] else obstacleGrid[i,j] = 0
1. Dynamic Programming¶
Intuition
The robot can only move either down or right. Hence any cell in the first row can only be reached from the cell left to it.
And, any cell in the first column can only be reached from the cell above it.
For any other cell in the grid, we can reach it either from the cell to left of it or the cell above it.
If any cell has an obstacle, we won’t let that cell contribute to any path.
We will be iterating the array from left-to-right and top-to-bottom. Thus, before reaching any cell we would have the number of ways of reaching the predecessor cells. This is what makes it a Dynamic Programming problem. We will be using the obstacleGrid array as the DP array thus not utilizing any additional space.
Note: As per the question, cell with an obstacle has a value 1. We would use this value to make sure if a cell needs to be included in the path or not. After that we can use the same cell to store the number of ways to reach that cell.
Algorithm
If the first cell i.e. obstacleGrid[0,0] contains 1, this means there is an obstacle in the first cell. Hence the robot won’t be able to make any move and we would return the number of ways as 0.
Otherwise, if obstacleGrid[0,0] has a 0 originally we set it to 1 and move ahead.
Iterate the first row. If a cell originally contains a 1, this means the current cell has an obstacle and shouldn’t contribute to any path. Hence, set the value of that cell to 0. Otherwise, set it to the value of previous cell i.e. obstacleGrid[i,j] = obstacleGrid[i,j-1]
Iterate the first column. If a cell originally contains a 1, this means the current cell has an obstacle and shouldn’t contribute to any path. Hence, set the value of that cell to 0. Otherwise, set it to the value of previous cell i.e. obstacleGrid[i,j] = obstacleGrid[i-1,j]
Now, iterate through the array starting from cell obstacleGrid[1,1]. If a cell originally doesn’t contain any obstacle then the number of ways of reaching that cell would be the sum of number of ways of reaching the cell above it and number of ways of reaching the cell to the left of it. obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]
If a cell contains an obstacle set it to 0 and continue. This is done to make sure it doesn’t contribute to any other path.
See: https://leetcode.com/problems/unique-paths-ii/solution/
[5]:
class Solution1(object):
"""
Time: O(M*N)
Space: O(1)
"""
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
m = len(obstacleGrid)
n = len(obstacleGrid[0])
# If the starting cell has an obstacle, then simply return as there would be
# no paths to the destination.
if obstacleGrid[0][0] == 1:
return 0
# Number of ways of reaching the starting cell = 1.
obstacleGrid[0][0] = 1
# Filling the values for the first column
for i in range(1,m):
obstacleGrid[i][0] = int(obstacleGrid[i][0] == 0 and obstacleGrid[i-1][0] == 1)
# Filling the values for the first row
for j in range(1, n):
obstacleGrid[0][j] = int(obstacleGrid[0][j] == 0 and obstacleGrid[0][j-1] == 1)
# Starting from cell(1,1) fill up the values
# No. of ways of reaching cell[i][j] = cell[i - 1][j] + cell[i][j - 1]
# i.e. From above and left.
for i in range(1,m):
for j in range(1,n):
if obstacleGrid[i][j] == 0:
obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
else:
obstacleGrid[i][j] = 0
# Return value stored in rightmost bottommost cell. That is the destination.
return obstacleGrid[m-1][n-1]
[6]:
s = Solution1()
obstacleGrid = [
[0,0,0],
[0,1,0],
[0,0,0]
]
assert s.uniquePathsWithObstacles(obstacleGrid) == 2
obstacleGrid = [[0]]
assert s.uniquePathsWithObstacles(obstacleGrid) == 1
2. Dynamic Programming¶
[7]:
class Solution2(object):
"""
Time: O(M*N)
Space: O(M+N)
"""
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
m, n = len(obstacleGrid), len(obstacleGrid[0])
ways = [0]*n
ways[0] = 1
for i in range(m):
if obstacleGrid[i][0] == 1:
ways[0] = 0
for j in range(n):
if obstacleGrid[i][j] == 1:
ways[j] = 0
elif j>0:
ways[j] += ways[j-1]
return ways[-1]
[8]:
s = Solution2()
obstacleGrid = [
[0,0,0],
[0,1,0],
[0,0,0]
]
assert s.uniquePathsWithObstacles(obstacleGrid) == 2
obstacleGrid = [[0]]
assert s.uniquePathsWithObstacles(obstacleGrid) == 1